package Array;

/**
 * 189. 轮转数组
 * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
   思路： 1：数组反转，这道题要用纸推导画一画规律，可以发现， 我们将原数组先全部反转，这样k个位置就可以从首位开始计算，
    接着将前k位和后n-k位的元素均反转，就得到了结果， 本质上是数学推导，代码翻译而已，时间复杂度O(n)，空间复杂度O(1)。
         2： 也可以用一个额外的数据，然后 (i+k)%n 赋值到新数组中，但是存在空间复杂度O(n)
   解题步骤：
       1： 数组n先全部反转
       2:  前K位数组反转
       3： 后n-k位数组反转
       4： 返回结果
 */
public class RotateArray {
    public void rotate(int[] nums, int k) {
        if(nums == null || nums.length<2){
            return;
        }
        // 如果数组大小小于k，直接对k取余
        if(nums.length < k){
            k = k%nums.length;
        }
        // 1：反转原数组
        for (int i = 0; i < nums.length/2; i++) {
            int temp = nums[i];
            nums[i] = nums[nums.length-1-i];
            nums[nums.length-1-i] = temp;
        }
        //2:反转前K个元素
        for (int i = 0; i < k/2; i++) {
            int temp = nums[i];
            nums[i] = nums[k-1-i];
            nums[k-1-i] = temp;
        }
        //3:反转后n-k个元素,用while更容易实现
        int i = k;
        int j = nums.length-1;
        while (j > i ){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }


    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7};
        RotateArray rotateArray = new RotateArray();

        rotateArray.rotate(nums,3);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
        System.out.println();
        int[] nums1 = {1,2};
        rotateArray.rotate(nums1,3);
        for (int i = 0; i < nums1.length; i++) {
            System.out.print(nums1[i]+" ");
        }
    }
}
